﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1_归并排序
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] a = { 3, 5, 6, 2, 3, 6, 9, 87, 1, 2, 5, 63, 2, 45, 0,6 };
            int[] b = MergerSort(a);

            foreach (var item in b)
            {
                Console.Write(item);
                Console.Write(" ");
            }
            Console.WriteLine();
            Console.ReadLine();
        }

        /// <summary>
        /// 归并排序
        /// </summary>
        static int[] MergerSort(int[] nums)
        {
            if (nums.Length == 1)
            {
                return nums;
            }

            int n = nums.Length / 2;
            int[] list1 = MergerSort(nums.Take(n).ToArray());
            int[] list2 = MergerSort(nums.Skip(n).ToArray()); // 当数组的个数大于1时，就将他分为两半，分别进行归并排序

            // 合并排序后的两个数组
            int[] result = new int[list1.Length + list2.Length];

            int t1 = 0; // list1 的下标
            int t2 = 0; // list2 的下标

            for (int i = 0; i < result.Length; i++)
            {
                if (t1 >= list1.Length)  // list1 全部取出，就从list2中取数字
                {
                    result[i] = list2[t2];
                    t2++;
                }
                else if (t2 >= list2.Length)  // list2 全部取出，就从list1中取数字
                {
                    result[i] = list1[t1];
                    t1++;
                }
                else  // 两个列表都有剩余数字，就取出小的那一个
                {
                    if (list1[t1] < list2[t2])
                    {
                        result[i] = list1[t1];
                        t1++;
                    }
                    else
                    {
                        result[i] = list2[t2];
                        t2++;
                    }
                }
            }

            return result;
        }
    }
}
